#!/usr/bin/env python
# -*- coding:utf-8 -*-
# @Author  : 邢建辉
# @Email   : xjh_0125@sina.com
# @Time    : 2022/1/11 17:37
# @Software: PyCharm
# @File    : l1095_find_in_mountain_array.py


# """
# This is MountainArray's API interface.
# You should not implement it, or speculate about its implementation
# """
class MountainArray:
    def __init__(self, arr):
        self.arr = arr

    def get(self, index: int) -> int:
        return self.arr[index]

    def length(self) -> int:
        return len(self.arr)


class Solution:
    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:
        dic = {}
        l = mountain_arr.length()

        def get(idx):
            if idx not in dic:
                dic[idx] = mountain_arr.get(idx)
            return dic[idx]

        def find_mid():
            left, right = 0, l
            while left < right:
                mid = (right + left) // 2
                if mid == 0:
                    break
                prev = mid - 1
                if get(mid) > get(prev):
                    if left == mid:
                        break
                    left = mid
                else:
                    right = mid - 1
            mid = mid + 1 if mid == 0 else mid
            mid = mid - 1 if mid == l - 1 else mid
            prev_v = get(mid - 1)
            mid_v = get(mid)
            next_v = get(mid + 1)
            if mid_v < prev_v:
                mid = mid - 1
            elif mid_v < next_v:
                mid += 1
            return mid

        def find_target(left, right, is_upper):
            while left <= right:
                mid = (left + right) // 2
                mid_v = get(mid)
                if mid_v > target:
                    if is_upper:
                        right = mid - 1
                    else:
                        left = mid + 1
                elif mid_v < target:
                    if is_upper:
                        left = mid + 1
                    else:
                        right = mid - 1
                else:
                    return mid
            return -1

        mid = find_mid()
        res = find_target(0, mid, True)
        if res == -1:
            res = find_target(mid, l - 1, False)
        return res



if __name__ == '__main__':
    s = Solution()
    arr = [3, 5, 3, 2, 0]
    target = 5
    m = MountainArray(arr)
    print(s.findInMountainArray(target, m))
